package top.humbleyuan.linkedlist;

import top.humbleyuan.datastructure.linkedlist.LinkNode;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 22:25
 * @Des 重排链表
 */
public class LeetCode_143 {
    /**
     * 重排链表
     * 1.找到重点（两种情况）
     * 2.将后半段逆序
     * 3.逆序后的后半段依次插入前半段
     */
    public static void main(String[] args) {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(1);
        int[] vals = {2,3,4};
        head = LinkNode.formLink(head,vals);

        LinkNode slow = head,fast = head;


        while (fast != null) {
            if(fast.next == null) {
                break;
            }

            slow = slow.next;
            fast = fast.next.next;
        }

        LinkNode inversePreTemp = slow;
        LinkNode inverseNextTemp = slow.next;

        inversePreTemp.next = null;
        //从slow(mid)往后逆置后半段链表
        while(inverseNextTemp != null) {

            LinkNode temp = inverseNextTemp.next;

            inverseNextTemp.next = inversePreTemp;
            inversePreTemp = inverseNextTemp;
            inverseNextTemp = temp;

        }

        LinkNode insertTemp = head;
        //inversePreNext为逆置后后半段的head
        while(inversePreTemp != null) {
            LinkNode temp1 = insertTemp.next;
            LinkNode temp2 = inversePreTemp.next;

            insertTemp.next = inversePreTemp;
            inversePreTemp.next = temp1;
            inversePreTemp = temp2;
            insertTemp = temp1;
        }

        slow.next = null;

        LinkNode.headToString(head);
    }
}
